#include <string>
#include <iostream>

#include "huffman.h"
#include "tree.h"
#include "binary_heap.h"
#include "list.h"

using namespace std;

Huffman::Huffman(string c)
{
    content = c;
}

Huffman::~Huffman()
{
    //dtor
}

int* Huffman::frequency()
{
    int size = content.length();
    int* t = new int[ASCII_SIZE];
    for(int i = 0; i < size; i++)
        t[content[i]]++;
    return t;
}

BinaryHeap Huffman::buildBinaryHeap()
{
    int* f = frequency();
    BinaryHeap heap(size() + 1);
    for(int i = 0; i < ASCII_SIZE; i++){
        if(f[i] != 0){
            Node* node = new Node;
            node->ch = (char) i;
            node->left = NULL;
            node->right = NULL;
            heap.insert(f[i], node);
        }
    }
    return heap;
}

Node* Huffman::buildHuffmanTree()
{
    BinaryHeap heap = buildBinaryHeap();
    while(heap.size() > 1){
        ItemBH i1 = heap.remove();
        ItemBH i2 = heap.remove();
        int freq = i1.freq + i2.freq;
        Node* node = new Node;
        node->left = i1.data;
        node->right = i2.data;
        heap.insert(freq, node);
    }
    return heap.remove().data;
}

int Huffman::size()
{
    if(quantity == 0){
        int* f = frequency();
        for(int i = 0; i < ASCII_SIZE; i++){
            if(f[i] != 0)
                quantity++;
        }
    }
    return quantity;
}

string* Huffman::buildCode(Node* n)
{
    string* l = new string[ASCII_SIZE];
     _buildCode(l, n, "");
     return l;
}

void Huffman::_buildCode(string* l, Node* n, string s)
{
    if(n != NULL){
        if(n->left == NULL && n->right == NULL){
            l[n->ch] =  s;
        } else {
            _buildCode(l, n->left, s + "0");
            _buildCode(l, n->right, s + "1");
        }
    }
}

string Huffman::compress()
{
    Node* tree = buildHuffmanTree();
    string* code_table = buildCode(tree);
    string result = "";
    for(int i = 0; i < content.length(); i++)
        result = result + code_table[content[i]];
    return result;
}
